/* Name: Cameron Hoerig
 * 
 * Date: 4-3-12
 * 
 * Description: The PriorityQueue class manages the operation of a priority queue. The queue
 * 	is stored as a heap. Users of the class have the option to add events to the queue, retrieve
 * 	the event with the highest priority, or get the size of the queue. Internally, the class contains
 * 	a private method for resorting the heap.
 * 
 * Revisions:
 * 4/3/12 - Cameron Hoerig - Original
 */
import java.util.*;

// The PriorityQueue class implements methods and members to keep a priority queue as a heap of Events
public class PriorityQueue {
	
	public PriorityQueue(){};
	
	// create a Linked List to act as the heap
	private LinkedList<Event> priorityQueue = new LinkedList<Event>();
	

	// add a new event to the priority queue
	public int push(String priority, String info){
		int newPriority = 0;
		try{
			newPriority = Integer.parseInt(priority);
		}
		catch(NumberFormatException nFE){
			return -1; // priority is not an integer, return error code
		}
		
		if(info.length() != 5){
			return -4; // info is not a 5 character string, return error code
		}
		else if(newPriority < 1){
			return -2; // priority is less than one, return an error
		}
		else if(newPriority > 200){
			return -3; // priority is greater than 200, return an error
		}
		else{
			priorityQueue.addLast(new Event(newPriority, info));
		}
		
		// now reorder heap to ensure proper sorting
		orderQueue();
		return 0;
		
	}
	
	// add a new event to the priority queue, checking to make sure the new event has a priority
	// greater than or equal to the priority of the event at the top of the heap
	public int pushSafe(String priority, String info){
		
		Event tempEvent = priorityQueue.get(1);	
		int newPriority = 0;
		
		try{
			newPriority = Integer.parseInt(priority);
		}
		catch(NumberFormatException nFE){
			return -1; // priority is not an integer, return error code
		}
		
		// if the priority of the new event is smaller than the root node or
		// greater than 200, do not add it to the queue
		if(newPriority < tempEvent.getPriority()){
			return -2;
		}
		else if( newPriority > 200){
			return -3;
		}
		else{
			int returnValue = push(priority, info);
			return returnValue;
		}
	}
	
	public Event pop(){
		// pull the first event from the queue and hold while reordering heap
		Event tempEvent = priorityQueue.removeFirst();
		// now reorder heap
		orderQueue();
		// return the event with the highest priority from the queue
		return tempEvent;		
	}
	
	public int getSize(){
		// return the size of the queue
		return priorityQueue.size();
	}
	
	// reorder the heap to ensure proper sorting
	private void orderQueue(){
		
		int queueLength = priorityQueue.size(); // get the size of the queue 
		boolean sorted = false; // at this time, the heap is not sorted
		int parentIndex = 0; // index of parent node
		int childIndex1 = 0; // index of left child node
		int childIndex2 = 0; // index of right child node
		int currentPriority = 0; // priority of the current event in question
		int childPriority1 = 0;  // priority of the left child node
		int childPriority2 = 0;  // priority of the right child node
		Event currentEvent;	 // current event object
		Event childEvent;		 // child event object
		
		while(sorted == false){
			sorted = true;
			for(int i = 0; i < queueLength; i++){
				parentIndex = i;
				currentEvent = priorityQueue.get(i); // retrieve the current event
				currentPriority = currentEvent.getPriority();
				childIndex1 = (i+1)*2-1; // calculate the position of the left child node
				childIndex2 = (i+1)*2;   // calculate the position of the right child node
				
				if(childIndex1 < queueLength){ // ensure an improper index is not going to be accessed
					childEvent = priorityQueue.get(childIndex1);
					childPriority1 = childEvent.getPriority();
					if(currentPriority > childPriority1){ // if parent priority is greater than child priority, swap the two nodes
						sorted = false; // heap is not sorted
						Event tempEvent = childEvent;
						priorityQueue.set(childIndex1,currentEvent); // remove right child node and replace with parent node
						priorityQueue.set(parentIndex, tempEvent);   // replace parent node with child node
						break; // restart at the top of the heap and reorder from that point
					}
				}
				if(childIndex2 < queueLength){ // ensure an improper index is not going to be accessed
					childEvent = priorityQueue.get(childIndex2);
					childPriority2 = childEvent.getPriority();
					if(currentPriority > childPriority2){ // if parent priority is greater than child priority, swap the two nodes
						sorted = false; // heap is not sorted
						Event tempEvent = childEvent;
						priorityQueue.set(childIndex2,currentEvent); // remove right child node and replace with parent node
						priorityQueue.set(parentIndex, tempEvent);   // replace parent node with child node
						break; // restart at the top of the heap and reorder from that point
					}
				}
				
			}
		}
		
	}

}
